/*  深度优先，实现迷宫遍历 */

#include<iostream>
#include<cstdlib>
#include<thread>
using namespace std;

const int mazeRow = 10;
const int mazeCol = 10;

char maze[mazeRow][mazeCol] =
{
	{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' },
	{ '#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#' },
	{ '#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#' },
	{ '#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#' },
	{ '#', ' ', '#', '#', '#', ' ', ' ', ' ', '#', '#' },
	{ '#', ' ', ' ', ' ', '#', ' ', ' ', ' ', '#', '#' },
	{ '#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#' },
	{ '#', '#', '#', '#', '#', ' ', '#', '#', ' ', '#' },
	{ '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', 'A', '#' },
	{ '#', '#', '#', '#', '#', '#', '#', '#', '#', '#' }
};
bool bVisited[mazeRow][mazeCol] = { false };

bool IsValidPos(int i, int j)
{
	return maze[i][j] != '#' && !bVisited[i][j];
}

void MazeDfs(int x, int y)
{
	int step[4][2] = {
		{0, 1},		//右
		{-1, 0},	//上
		{0, -1},	//左
		{1, 0}		//下
	};

	if (maze[x][y] == 'A')
	{
        this_thread::sleep_for(1000ms);
        system("clear");
		for (int i = 0; i < mazeRow; ++i)
		{
			for (int j = 0; j < mazeCol; ++j)
			{
				cout << maze[i][j] << " ";
			}
			cout << endl;
		}
		return;
	}

	for (int k = 0; k < 4; k++)
	{
		int tx = x + step[k][0];
		int ty = y + step[k][1];

		if (!IsValidPos(tx, ty))
		{
			continue;
		}

		bVisited[tx][ty] = 1;
		maze[x][y] = '*';
		MazeDfs(tx, ty);
		maze[x][y] = ' ';
		bVisited[tx][ty] = 0;
	}
}

int main(void)
{
	for (int i = 0; i < mazeRow; ++i)
	{
		for (int j = 0; j < mazeCol; ++j)
		{
			cout << maze[i][j] << " ";
		}
		cout << endl;
	}

	bVisited[1][1] = true;
	MazeDfs(1, 1);
}
